Deutsch–Jozsa Algorithm
   HOME

TheInfoList



OR:

The Deutsch–Jozsa algorithm is a
deterministic Determinism is the metaphysical view that all events within the universe (or multiverse) can occur only in one possible way. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping mo ...
quantum algorithm In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite seq ...
proposed by
David Deutsch David Elieser Deutsch ( ; ; born 18 May 1953) is a British physicist at the University of Oxford, often described as the "father of quantum computing". He is a visiting professor in the Department of Atomic and Laser Physics at the Centre for ...
and
Richard Jozsa Richard Jozsa is an Australian mathematician who holds the Leigh Trapnell Chair in Quantum Physics at the University of Cambridge. He is a fellow of King's College, Cambridge, where his research investigates quantum information science. A pion ...
in 1992 with improvements by
Richard Cleve Richard Erwin Cleve is a Canadian professor of computer science at the David R. Cheriton School of Computer Science at the University of Waterloo, where he holds the Institute for Quantum Computing Chair in quantum computing, and an associate me ...
,
Artur Ekert Artur Konrad Ekert (born 19 September 1961) is a British / Polish professor of quantum physics at the Mathematical Institute, University of Oxford, professorial fellow in quantum physics and cryptography at Merton College, Oxford, Lee Kong Chi ...
, Chiara Macchiavello, and Michele Mosca in 1998. Although of little practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. The Deutsch–Jozsa problem is specifically designed to be easy for a quantum algorithm and hard for any deterministic classical algorithm. It is a
black box In science, computing, and engineering, a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics), without any knowledge of its internal workings. Its implementation is "opaque" (black). The te ...
problem that can be solved efficiently by a quantum computer with no error, whereas a deterministic classical computer would need an exponential number of queries to the black box to solve the problem. More formally, it yields an oracle relative to which EQP, the class of problems that can be solved exactly in polynomial time on a quantum computer, and P are different. Since the problem is easy to solve on a probabilistic classical computer, it does not yield an oracle separation with BPP, the class of problems that can be solved with bounded error in polynomial time on a probabilistic classical computer. Simon's problem is an example of a problem that yields an oracle separation between BQP and BPP.


Problem statement

In the Deutsch–Jozsa problem, we are given a black box quantum computer known as an
oracle An oracle is a person or thing considered to provide insight, wise counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. If done through occultic means, it is a form of divination. Descript ...
that implements some function: f \colon\^n \to \ The function takes n-bit binary values as input and produces either a 0 or a 1 as output for each such value. We are promised that the function is either constant (0 on all inputs or 1 on all inputs) or ''balanced'' (1 for exactly half of the input domain and 0 for the other half). The task then is to determine if f is constant or balanced by using the oracle.


Classical solution

For a conventional
deterministic Determinism is the metaphysical view that all events within the universe (or multiverse) can occur only in one possible way. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping mo ...
algorithm where n is the number of bits, 2^ + 1 evaluations of f will be required in the worst case. To prove that f is constant, just over half the set of inputs must be evaluated and their outputs found to be identical (because the function is guaranteed to be either balanced or constant, not somewhere in between). The best case occurs where the function is balanced and the first two output values are different. For a conventional
randomized algorithm A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
, a constant k evaluations of the function suffices to produce the correct answer with a high probability (failing with probability \epsilon \leq 1/2^ with k \geq 1). However, k=2^ + 1 evaluations are still required if we want an answer that has no possibility of error. The Deutsch-Jozsa quantum algorithm produces an answer that is always correct with a single evaluation of f.


History

The Deutsch–Jozsa algorithm generalizes earlier (1985) work by David Deutsch, which provided a solution for the simple case where n = 1 .
Specifically, finding out if a given
Boolean function In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth functi ...
whose input is one bit, f: \ \to \, is constant. The algorithm, as Deutsch had originally proposed it, was not deterministic. The algorithm was successful with a probability of one half. In 1992, Deutsch and Jozsa produced a deterministic algorithm which was generalized to a function which takes n bits for its input. Unlike Deutsch's algorithm, this algorithm required two function evaluations instead of only one. Further improvements to the Deutsch–Jozsa algorithm were made by Cleve et al., resulting in an algorithm that is both deterministic and requires only a single query of f. This algorithm is still referred to as Deutsch–Jozsa algorithm in honour of the groundbreaking techniques they employed.


Algorithm

For the Deutsch–Jozsa algorithm to work, the oracle computing f(x) from x must be a quantum oracle which does not decohere x. In its computation, it cannot make a copy of x, because that would violate the no cloning theorem. The point of view of the Deutsch-Jozsa algorithm of f as an oracle means that it does not matter what the oracle does, since it just has to perform its promised transformation. The algorithm begins with the n+1 bit state , 0\rangle^ , 1\rangle . That is, the first n bits are each in the state , 0\rangle and the final bit is , 1\rangle . A
Hadamard gate The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
is applied to each bit to obtain the state \frac\sum_^ , x\rangle (, 0\rangle - , 1\rangle ), where x runs over all n-bit strings, which each may be represented by a number from 0 to 2^n - 1. We have the function f implemented as a quantum oracle. The oracle maps its input state , x\rangle, y\rangle to , x\rangle, y\oplus f(x) \rangle , where \oplus denotes addition modulo 2. Applying the quantum oracle gives; \frac \sum_^ , x\rangle (, 0\oplus f(x)\rangle - , 1\oplus f(x)\rangle ). For each x, f(x) is either 0 or 1. Testing these two possibilities, we see the above state is equal to \frac\sum_^ (-1)^ , x\rangle (, 0\rangle - , 1\rangle ). At this point the last qubit \frac may be ignored and the following remains: \frac\sum_^ (-1)^ , x\rangle. Next, we will have each qubit go through a
Hadamard gate The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
. The total transformation over all n qubits can be expressed with the following identity: H^ , k\rangle = \frac \sum_^ (-1)^ , j\rangle (j\cdot k = j_0 k_0\oplus j_1 k_1\oplus\cdots\oplus j_ k_ is the sum of the bitwise product). This results in \frac \sum_^(-1)^ \left y\rangle \right= \sum_^ \left \frac \sum_^(-1)^ (-1)^\right, y\rangle . From this, we can see that the probability for a state k to be measured is \left, \frac \sum_^ ^ ^ \^2 The probability of measuring k = 0 , corresponding to , 0\rangle^, is \bigg, \frac\sum_^(-1)^\bigg, ^2 which evaluates to 1 if f(x) is constant (
constructive interference In physics, interference is a phenomenon in which two coherence (physics), coherent waves are combined by adding their intensities or displacements with due consideration for their phase (waves), phase difference. The resultant wave may have ...
) and 0 if f(x) is balanced (
destructive interference In physics, interference is a phenomenon in which two coherent waves are combined by adding their intensities or displacements with due consideration for their phase difference. The resultant wave may have greater amplitude (constructive in ...
). In other words, the final measurement will be , 0\rangle^ (all zeros) if and only if f(x) is constant and will yield some other state if f(x) is balanced.


Deutsch's algorithm

Deutsch's algorithm is a special case of the general Deutsch–Jozsa algorithm where n = 1 in f\colon\^n\rightarrow \. We need to check the condition f(0)=f(1). It is equivalent to check f(0)\oplus f(1) (where \oplus is addition modulo 2, which can also be viewed as a quantum
XOR gate XOR gate (sometimes EOR, or EXOR and pronounced as Exclusive OR) is a digital logic gate that gives a true (1 or HIGH) output when the number of true inputs is odd. An XOR gate implements an exclusive disjunction, exclusive or (\nleftrightarrow) ...
implemented as a
Controlled NOT gate In computer science, the controlled NOT gate (also C-NOT or CNOT), controlled-''X'' gate, controlled-bit-flip gate, Feynman gate or controlled Pauli-X is a quantum logic gate that is an essential component in the construction of a gate-based qu ...
), if zero, then f is constant, otherwise f is not constant. We begin with the two-qubit state , 0\rangle , 1\rangle and apply a
Hadamard gate The Hadamard transform (also known as the Walsh–Hadamard transform, Hadamard–Rademacher–Walsh transform, Walsh transform, or Walsh–Fourier transform) is an example of a generalized class of Fourier transforms. It performs an orthogonal ...
to each qubit. This yields \frac(, 0\rangle + , 1\rangle)(, 0\rangle - , 1\rangle). We are given a quantum implementation of the function f that maps , x\rangle , y\rangle to , x\rangle , f(x)\oplus y\rangle. Applying this function to our current state we obtain \begin & \frac(, 0\rangle(, f(0)\oplus 0\rangle - , f(0)\oplus 1\rangle) + , 1\rangle(, f(1)\oplus 0\rangle - , f(1)\oplus 1\rangle)) \\ &=\frac((-1)^, 0\rangle(, 0\rangle - , 1\rangle) + (-1)^, 1\rangle(, 0\rangle - , 1\rangle)) \\ &=(-1)^\frac\left(, 0\rangle + (-1)^, 1\rangle\right)(, 0\rangle - , 1\rangle). \end We ignore the last bit and the global phase and therefore have the state \frac(, 0\rangle + (-1)^, 1\rangle). Applying a Hadamard gate to this state we have \begin &\frac (, 0\rangle + , 1\rangle + (-1)^, 0\rangle - (-1)^, 1\rangle) \\ &=\frac ((1 +(-1)^) , 0\rangle + (1-(-1)^) , 1\rangle). \end f(0)\oplus f(1) = 0 if and only if we measure , 0\rangle and f(0)\oplus f(1)=1 if and only if we measure , 1\rangle. So with certainty we know whether f(x) is constant or balanced.


Deutsch–Jozsa algorithm Qiskit implementation

The quantum circuit shown here is fro
a simple example of how the Deutsch–Jozsa algorithm can be implemented in Python
using Qiskit, an open-source quantum computing software development framework by IBM.


See also

* Bernstein–Vazirani algorithm


References


External links


Deutsch's lecture about the Deutsch-Jozsa algorithm
{{DEFAULTSORT:Deutsch-Jozsa algorithm Quantum algorithms